\section{Introducci\'on}
El joyero Frank O. Yar tiene que fabricar una serie de piezas de orfebrería. El problema es que el precio al que puede vender cada pieza de joya va perdiendo valor con el pasar de los días. 
Por cada día que tarde en entregar la pieza $p_i$ va a tener una pérdida $d_i$ de dinero. 
Con cada pieza de joya $p_i$, viene asociada también un tiempo de fabricación $t_i$. Solo se puede realizar una sola pieza a la vez.
En este problema lo que se quiere realizar es minimizar la perdida de dinero de el joyero Frank O.
\\
Para ello contamos con los siguientes datos:

\begin{itemize}
\item Un entero \textbf{n} $\rightarrow$ Representar\'a el n\'umero de piezas a fabricar.
\item Para cada una de esas piezas tenemos:

\begin{itemize}
\item Un entero \textbf{d}\_i $\rightarrow$ Representar\'a la perdida diaria de ganancia.
\item Un entero \textbf{t}\_i $\rightarrow$ Representar\'a el tiempo que tarda en fabricar la pieza.
\end{itemize}
\end{itemize}

\subsection{Ejemplo Ilustrativo}

Una instancia del problema podr\'ia ser, por ejemplo, $$n = 4,~d_1=1,~t_1=7,~d_2=3,~t_2=5,~d_3=5,~t_3=3,~d_4=7,~t_4=1.$$
\\
Para este caso la soluci\'on que minimiza la perdida de ganancia es primero fabricar la pieza $4$, luego la $3$, luego la $2$ y finalmente la $1$. 
\\
\\
En ese caso habr\'a perdido:
$$d_4*t_4 +d_3*(t_4+t_3) + d_2*(t_2+d_3+t_4) + d_1*(t_1 + t_2+t_3+t_4) =  7*1+5*(3+1)+3*(1+3+5) + 1 * (1+3+5+7) = 70$$
\\
En cualquier otra combinaci\'on se obtendr\'ia una perdida de ganancia mayor. \\
Calculemos por elemplo el caso en que se toman las piezas en el orden $1,2,3,4$, la perdida ser\'a: $$1*7+3*(7+5)+5*(7+5+3)+7*(7+5+3+1) = 230$$
Luego la perdida es mayor.



\section{Idea General de Resoluci\'on}

Para la resoluci\'on de este problema se utilizar\'a el concepto de algoritmo goloso. El mismo consiste en elegir la soluci\'on \'optima en cada paso local con la esperanza de llegar a una soluci\'on general \'optima, en este caso la cantidad m\'inima de dinero perdido.
\\
\\
La correctitud de este algoritmo ser\'a probada m\'as adelante, por ahora supondremos que el algoritmo nos d\'a la mejor posible siempre.
\\
\\
Luego, la idea general que seguir\'a el algoritmo es la siguiente:
\\
\\
Para cada pieza, calcula la p\'erdida de la pieza dividido los d\'ias que tarda en hacerla, esto es $pd_i=\frac{di}{ti}$. \\
Luego ordena las piezas decrecientemente de acuerdo a este coefienciente calculado, y se obtiene el resultado.

\subsection{Ejemplo Del Algoritmo}

A modo de ejemplo, veamos como actua el algoritmo con el ejemplo dado en la introducc\'on:
\\
Tenemos  $n = 4$, $d_1=1$, $t_1=7$, $d_2=3$, $t_2=5$, $d_3=5$, $t_3=3$, $d_4=7$, $t_4=1$.
\\
\\
Calculo cada uno de los coeficientes de las piezas:

$pd_1 = 1/7$

$pd_2 =  3/5$

$pd_3  = 5/3$

$pd_4 = 7$
\\
\\
Luego ordenandolas de mayor a menor se obtiene que las piezas se deben fabricar en el orden $4,3,2,1$

\section{Correctitud}

En esta secci\'on probaremos que la lista entregada por el algoritmo goloso es una soluci\'on \'optima que minimiza la perdida de Frank:

\begin{itemize}
\item Supongamos una solución óptima con un orden distinto al propuesto por el algoritmo: esto quiere decir que no necesariamente esta ordenado por \textit{pdi} descendente.
\item Tomamos $S_1,S_2,S_3,...S_n$ como los $n$ elementos de la lista $S_A$ ordenados de alguna manera por el algoritmo
\item El costo de hacer la pieza de la posici\'on $1$ ($S_1$) es $d_1*t_1$,la de hacer la $S_2$ es $ d_2*(t_1+t_2)$, la de $S_3$, $ d_3*(t_1+t_2+t_3)$ y as\'i sucesivamente para cada elemento.
\item Dado que la lista no est\'a ordenada necesariamente de la manera propuesta, el algoritmo no nos asegura que $pd_{s1} \geq pd_{s2} \geq pd_{s3} \geq pd_{s4}\geq ... \geq pd_{sn} $
\item Entonces como la lista no nos asegura este orden, en alg\'un momento dos elementos consecutivos de la lista $S$ ser\'an $S_i < S_{j}$ para alguna posici\'on $i,j$ consecutivos.
\item Al ocurrir esto, que pasa si permutamos este par de elementos de tal manera que queden ordenados en la lista de la siguiente manera y llamamos a esta nueva lista $S_B$ : $S_B = S_1,...,S_j,S_i,...,S_n$, donde $S_j \geq S_i$.
\item $S_A$ es una solución óptima por hipótesis, de manera que la suma total de todos los costos en $S_A$ es menor igual a la de $S_B$.
\item costo total de $S_A$: $\displaystyle\sum_{k=1}^n {d_{k} (\displaystyle\sum_{l=1}^k t_{l} )}  $  $\leq$   costo total de $S_B$: $\displaystyle\sum_{k=1}^n {d_k (\displaystyle\sum_{l=1}^k t_l)}$
\item Luego la diferencia de costos entre $S_A$ y $S_B$ es: $\Delta S_{A,B} = costoTotalDe S_A - costoTotalDe S_B$.
\item En $S_B$ el costo de $S_1$ sigue siendo exactamente el mismo que en $S_A$ ($d_1*t_1$), lo mismo para todos los anteriores a $S_j$ en $S_B$.
\item Lo mismo para los elementos posteriores a $S_i$ en $S_B$.
$$ \Delta S_{A,B} = d_i*(t_1+...+t_i) + d_j*(t_1+...+t_i+t_j)  -  [ d_j*(t_1+...+t_j) + d_i*(t_1+...+t_j+t_i)]$$.
$$ \Delta S_{A,B} = d_i*t_1 +...+ d_i*t_i  +  d_j*t_1+...+d_j*t_i+d_j*t_j  - d_j*t_1-...-d_j*t_j - d_i*t_1-...-d_i*t_j-d_i*t_i $$
$$ \Delta S_{A,B} = +d_j*t_i - d_i*t_j <  0$$ (la diferencia es negativa ya que suponemos $S_A$ como menor costo que $S_B$)
\item Sabemos que además $pd_j \geq pd_i$, si y solo si $ \frac{dj}{tj} \geq \frac{di}{ti}$ cada $d_k$ y $t_k$ son positivos, entonces:
$$ d_j*t_i \geq d_i*t_j  \leftrightarrow  d_j*t_i - d_i*t_j \geq 0 $$
y esto es absurdo porque contradice $\Delta S_{A,B}$, el absurdo vino de suponer que $S_A$ era la solución óptima.
\item Ahora ya que sabemos que $S_B$ tiene un resultado mejor al ordenar $S_j$ y $S_i$, podemos seguir ordenando dos elementos consecutivos y darnos cunta que cada vez que modificamos esa lista, encontramos un resultado mejor.
\item Entonces llegamos a la conclusión que dado un orden distinto al propuesto por nosotros (orden decreciente de $Pd_i$), siempre podemos encontrar una lista mejor, al ir ordenandolo de esta manera.
\item Concluimos que el orden propuesto es el mejor para minimizar los costos de producción.

\end{itemize}

\section{Cota de Complejidad}
Lo que hace b\'asicamente el algoritmo es lo siguiente:

\subsection{Pseudoc\'odigo}

\begin{algorithm}
\begin{algorithmic}[1]\parskip=1mm
\caption{void funcionPrincipal()}

  \STATE{leer las entradas y crear el $vector <Joyas>$}
  \STATE{Ordenar $vector <Joyas>$ de mayor a menor por $pd_i$}
  \STATE{Calcular la perdida Total de acuerdo a ese orden}
  

\end{algorithmic}
\end{algorithm}

\begin{itemize}
\item Para ordenar de mayor a menor por $Pd_i$ usamos la función \textit{sort} para \textit{vector} de la \textit{Biblioteca Estandar}, cuya complejidad es O(nlog(n)). 
\item Una vez ordenado, calcular la perdida es hacer un barrido lineal al vector para calcular la perdida total.
\end{itemize}

Entonces \textit{T(n)} = donde \textit{n} es la cantidad de joyas a fabricar se calcula f\'acil:\\
\\
$T(n) = t(crearVector) + t(ordenar) + t(calcularPerdida)$
\\
$T(n) = n + n(log(n)) + n = max(n, n log(n))$
\\
$T(n) = n log (n)$ 
\\
Con lo cual queda $O(n log(n))$

\section{Casos de Test}

\subsection{Caso random}

Para testear la correctitud de nuestro algoritmo se cre\'o un generador de entradas que fabricar\'a 100 instancias random con N joyas y comparara nuestra salida con la de otro algoritmo creado por nosotros que resolviera el problema utilizando fuerza bruta pero con una complejidad mas alta.\\
\\
Los resultados comprobaron que nuestro algoritmo devuelve la soluci\'on correcta en todos los casos.
\\
\\
Ejemplo de caso random: (Este en particular tambi\'en fue verificado a mano)
\\
\\
\begin{tabular}{| l | l |}
\hline
~~Entrada\\ \hline
$
\begin{vmatrix}
~~6  &  ~~\\
~~5  & 2   ~~ \\
~~10 & 1   ~~ \\
~~1  & 15   ~~ \\
~~2  & 2   ~~ \\
~~5  & 5 ~~ \\
~~15 & 2 ~~ \\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\quad \quad \quad
\begin{tabular}{| l | l |}
\hline
~~~~~~~~~~~~~~Salida\\ \hline
$
\begin{vmatrix}
~~2  & 6  & 1  & 4  & 5  & 3  & 181 ~~\\
\end{vmatrix}
$
\\ \hline
\end{tabular}

\subsection{Un solo trabajo}

\begin{tabular}{| l | l |}
\hline
~~Entrada\\ \hline
$
\begin{vmatrix}
~~1  &  ~~\\
~~15 & 3   ~~ \\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\quad \quad \quad
\begin{tabular}{| l | l |}
\hline
~~~Salida\\ \hline
$
\begin{vmatrix}
~~1  & 45 ~~\\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\\
\\
Chequeamos que no falle para el caso borde donde solo hay una joya y la soluci\'on es trivial.

\subsection{Todos la misma relaci\'on}

\begin{tabular}{| l | l |}
\hline
~~Entrada\\ \hline
$
\begin{vmatrix}
~~5  &  ~~\\
~~14 & 7   ~~ \\
~~6  & 3   ~~ \\
~~10 & 5   ~~ \\
~~4  & 2   ~~ \\
~~2  & 1   ~~ \\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\quad \quad \quad
\begin{tabular}{| l | l |}
\hline
~~~~~~~~~~~~Salida\\ \hline
$
\begin{vmatrix}
~~1  & 2  & 3  & 4  & 5  & 142 ~~\\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\\
\\
Caso borde donde $\frac{di}{ti}$ es igual para todas las joyas. Luego cualquier combinaci\'on costar\'a lo mismo.

\section{Resultados}

Para gr\'aficar los tiempos de ejcuci\'on de nuestro algoritmo se fue variando la cantidad de joyas.\\
Para cada cantidad se crearon 20 instancias diferentes y luego se calcul\'o el promedio
\\
\includegraphics[width=18cm]{./laJoya/graph_ej2_2.png}
\\
\includegraphics[width=18cm]{./laJoya/graph_ej2_1.png}
\\
Como podemos ver el tiempo de ejcuci\'on es casi lineal con respecto a la cantidad de joyas.

\section{Adicionales}
Esta vez el joyero Frank, quiere descanzar un tiempo $r_i$ despues de realizar y entregar la joya $j_i$. 
Este tiempo de descanzo, no será incluido dentro de la fabricación de la joya $j_i$, ya que antes del descanzo entrega primero la joya. 
Sin embargo, esto afectará el tiempo de entrega de las joyas posteriores a ella. Aumentando la pérdida.


Se nos pide desarrollar los siguientes puntos:

\begin{enumerate}
\item ¿Cómo debería modificarse el algoritmo implementado?. 

\begin{itemize}
\item Anteriormente ordenabamos las joyas en orden decreciente a lo que definimos como $Pd_i = (d_i/t_i)$).
\item Para esta modificación, proponemos ordenarlos decrecientemente por lo que llamaremos $Pdr_i = d_i/(t_i+r_i)$
\item El resto del algoritmo es exactamente el mismo, unicamente cambia la manera de ordenarlos, con lo cual la complejidad tampoco cambia.
\end{itemize}

\item Dar la idea de como demostraría la correctitud. 
\begin{itemize}
\item La correctitud sigue exactamente la misma idea que en el problema original.
\item Imaginar que sigue otro orden (orden distinto a $Pdr_1 \geq Pdr_2 \geq Pdr_1 ...$).
\item Luego al estar ordenado distinto, seguro hay dos elementos consecutivos tal que $Pdr_i \leq Pdr_j$.
\item Y permutamos, hacemos exactamente las mismas cuentas y llegamos al mismo absurdo.
\item Luego no era la mejor manera de ordenar la secuencia de joyas, y podemos seguir ordenandolas hasta llegar a la solución propuesta por nosotros.

\end{itemize}

\end{enumerate}
